An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed half-lines) in the plane. Such a graph is 3-directional if every vertical ray has the same direction, and 2-directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomial-time algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2-directional orthogonal ray graphs, the dominating set problem can be solved in O(n2 log5 n) time, the weighted dominating set problem can be solved in O(n4 log n) time, and the number of dominating sets of a fixed size can be computed in O(n6 log n) time, where n is the number of vertices in the graph. We also show that for 2-directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n2+m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3-directional orthogonal ray graphs, the induced matching problem can be solved in O(m2) time, the weighted induced matching problem can be solved in O(m4) time, and the strong edge coloring problem can be solved in O(m3) time. We finally show that the weighted induced matching problem can be solved in O(m6) time for orthogonal ray graphs.

Irreversible k-conversion set is introduced in connection with the mathematical modeling of the spread of diseases or opinions. We show that the problem to find a minimum irreversible 2-conversion set can be solved in O(n2log 6n) time for graphs with maximum degree at most 3 (subcubic graphs) by reducing it to the graphic matroid parity problem, where n is the number of vertices in a graph. This affirmatively settles an open question posed by Kyncl et al. (2014).

For a given N-vertex graph H, a graph G obtained from H by adding t vertices and some edges is called a t-FT (t-fault-tolerant) graph for H if even after deleting any t vertices from G, the remaining graph contains H as a subgraph. For the n-dimensional cube Q(n) with N vertices, a t-FT graph with an optimal number O(tN+t2) of added edges and maximum degree of O(N+t), and a t-FT graph with O(tNlog N) added edges and maximum degree of O(tlog N) have been known. In this paper, we introduce some t-FT graphs for Q(n) with an optimal number O(tN+t2) of added edges and small maximum degree. In particular, we show a t-FT graph for Q(n) with 2ctN+ct2((logN)/C)C added edges and maximum degree of O(N/(logC/2N))+4ct.

It is a fundamental problem to construct a virtual path layout minimizing the hop number as a function of the congestion for a communication network. It is known that we can construct a virtual path layout with asymptotically optimal hop number for a mesh of trees network, butterfly network, cube-connected-cycles network, de Bruijn network, shuffle-exchange network, and complete binary tree network. The paper shows a virtual path layout with minimum hop number for a complete binary tree network. A generalization to complete k-ary tree networks is also mentioned.

Given a plane graph G, a trail of G is said to be dual if it is also a trail in the geometric dual of G. We show that the problem of partitioning the edges of G into the minimum number of dual trails is NP-hard.

The harmonious coloring of an undirected simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem to find the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are also known as caterpillars. This paper shows the harmonious chromatic number of a caterpillar with at most one vertex of degree more than 2. We also show the upper bound of the harmonious chromatic number of a 3-regular caterpillar.

The 3-D channel routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the top and bottom layers. A net is a set of terminals to be connected. The objective of the 3-D channel routing problem is to connect the terminals in each net with a Steiner tree (wire) in G using as few layers as possible and as short wires as possible in such a way that wires for distinct nets are disjoint. This paper shows that the problem is intractable. We also show that a sparse set of ν 2-terminal nets can be routed in a 3-D channel with O(√ν) layers using wires of length O(√ν).

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number Δ(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Δ(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by QN and DN respectively, we show, among others, that Δ(t, QN) = O(tN log(log N/t + log 2e)) for any t and N (t 2), and Δ(1, DN) = N/2 for N even.

For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.

Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.

This paper presents a practical fault-tolerant architecture for mesh parallel machines that has t spare processors and has 2(t+2) communication links per processor while tolerating at most t+1 processor and link faults. We also show that the architecture presented here can be laid out efficiently in a linear area with wire length at most O(t).

This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.

A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n3) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.

The finite reconfigurability and local reconfigurability of graphs were proposed by Sha and Steiglitz [1], [2] in connection with a problem of on-line reconfiguraion of WSI networks for run-time faults. It is shown in [2] that a t-locally-reconfigurable graph for a 2-dimensional N-vertex array AN can be constructed from AN by adding O(N) vertices and edges. We show that Ω(N) vertices must be added to an N-vertex graph GN in order to construct a t-locally-reconfigurable graph for GN, which means that the number of added vertices for the above mentioned t-locally-reconfigurable graph for AN is optimal to within a constant factor. We also show that a t-finitely-reconfigurable graph for an N-vertex graph GN can be constructed from GN by adding t vertices and tN + t (t+1)/2 edges.

This note shows an efficient implementation of de Bruijn networks by the Optical Transpose Interconnection System (OTIS) extending previous results by Coudert, Ferreira, and Perennes [2].

In this paper we show that an outerplanar graph G with maximum degree at most 3 has a 2-D orthogonal drawing with no bends if and only if G contains no triangles. We also show that an outerplanar graph G with maximum degree at most 6 has a 3-D orthogonal drawing with no bends if and only if G contains no triangles.

The logic mapping problem and the problem of finding a largest sub-crossbar with no defects in a nano-crossbar with nonprogrammable-crosspoint defects and disconnected-wire defects are known to be NP-hard. This paper shows that for nano-crossbars with only disconnected-wire defects, the former remains NP-hard, while the latter can be solved in polynomial time.

The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.